This invention relates in general to computer-based simulation systems and in particular to a system employing constraint satisfaction for temporizing a simulation.
Computer programs have long been used for simulating the behavior of a "real world" apparatus or process and an "animation" is a simulation which includes a graphical display representing the behavior of the apparatus or process. A computer simulation of a bouncing ball might include an algorithm for computing data representing the vertical position of the ball as a function of time. The data may then be used in a display.
In addition to simulating real world appearance of things, animation is a powerful means for representing the inner workings of a process which in itself does not have a visual aspect. For example, data structures are often represented by two dimensional diagrams because they are most easily apprehended in spatial, visual form rather than as a textual description or bits in a memory bank. By extension, understanding obscure algorithms operating on data structures could be assisted through simulation of dynamic motion in such diagrams and images.
Much of the appeal of animation is in being able to simulate the behavior of an experimental design to "see how it works." For instance, if an algorithm sorts bars by length, it is helpful to see the bars move about as they are sorted. However, this appeal is diminished if an animation is laborious to construct.
Experience has shown that about 80% of the code in computer-based animation merely implements animation graphics, even in an object oriented computer language like Smalltalk-80 (hereinafter referred to as "Smalltalk") which offers a high level graphics interface. ("Smalltalk-80" is a registered trademark of the Xerox Corporation and the Smalltalk computer language is described in the book SMALLTALK-80 The Language and Its Implementation, by Adele Goldberg and David Robson, published in 1983.
Animation difficulties are further magnified if one insists an animation must be more than pictures on a screen, and that the pictures should create the illusion of things they represent for allowing a user to interact with them. For example, an animated spring desirably acts like a real one in that a user should be able to "push" it or "pull" it and observe the response. This means the animation must be designed as a fully interactive interface and the user should be able to gain access to the code which drives the animation.
The requirements outlined above suggest the components for assembling an animation should be self-contained objects simulating "things" they represent. The internal state of each object should be self-consistent, in keeping with the real-world laws governing the item being simulated, and the picture of the object should change state consistently, according to the rules of some representational scheme. One may think of an animation as the creation of an image whose state is "constrained" to bear some specified relation to the state of an object simulating a "thing".
This need for consistency of state and representation makes the use of a constraint language desirable to implement animation. Constraint languages allow the programmer to declare relations that a system of objects must satisfy; it is the job of constraint satisfaction algorithms to automatically find a way to satisfy those relationships. The declarative character is attractive since it tends to reduce the creation of an animation to the writing of an executable specification, which one may expect to be simpler than writing out detailed graphics instructions in an imperative language.
One existing constraint oriented computer programming system, "ThingLab", is described in "ThingLab--A Constraint-Oriented Simulation Laboratory", by A. H. Borning, published July, 1979 by Xerox Corporation, in Xerox Palo Alto Research Center Report SSL-79-3, and in an article entitled "The Programming Language Aspects of ThingLab, A Constraint-Oriented Simulation Laboratory", also by A. H. Borning, published in ACM Transactions on Programming Languages and Systems, October, 1981. Constraints in ThingLab are implemented as objects that represent some relation as a predicate and contain a variety of methods as code fragments which can be used to establish the relation under different circumstances, depending on what is known. For example, a constraint predicate that a=b+c would contain the expressions a.rarw.b+c, b.rarw.a-c and c.rarw.a-b, any one of which may be used to satisfy the constraint. But depending upon what values are known or have just been changed, only one expression may be appropriate. The goal of constraint satisfaction techniques is to choose and order appropriate methods so that relations throughout a network of constraints are reestablished following a change.
The act of programming in a constraint oriented system consists of specifying, preferably in a graphical way, the interconnections among objects containing code fragments embodying the functionality of the part. The job of the constraint system then is to sort out and order those code fragments so that the composite shows the desired behavior of a coherent whole. One of the most attractive features of constraint languages is that they are fundamentally descriptive as opposed to imperative. The drudgery of hand-coding animations is in having to give explicitly imperative commands for everything that is to happen and appear on the screen. It is easier to merely describe in general terms how things should appear and let the system generate the code that would make it so.
The animated, dynamic responses of a system like ThingLab are user driven in response only to a command to "satisfy all constraints with these values now". Constraints in ThingLab are "static" rather than "temporal" in that they are satisfied in the same way for all time and are independent of time. There can be no history-dependent specifications because there is no history.